import fileinput
import math


def try12():
    itemset={}
    MIN_SUPPORT=0.01
    ERROR_BOUND=MIN_SUPPORT/10
    BUCKET_SIZE=math.ceil(1/ERROR_BOUND)
    print BUCKET_SIZE
    bucket_count=1
    count=0
    rec_count=0
    average=0
    no_request=0
    n=0
    value=()
    for line in fileinput.input(['D:\\A.txt']):
        n=n+1
        line2= line.strip().rstrip(',')
        item_list=line2.split(',')
        item_tuple=tuple(item_list)
        length=len(item_list)-1
        if(n<190000):
            if((n%BUCKET_SIZE)==0):
                bucket_count+=1
                print "count:",bucket_count
                itemset=prune(itemset,bucket_count)

            if(itemset.has_key(item_tuple)):
                value=itemset.get(item_tuple)
                count=value[0]
                count+=1
                itemset[item_tuple]=(count,(bucket_count-1))   
            else:
                itemset[item_tuple]=(1,(bucket_count-1))
        if(n>=190000):
            for i in range(0,length):
                no_request+=1
                j=i+1
                recommend_list=recommend(item_list[0:j],itemset)
                len1=len(recommend_list)
                if not len1==0:
                        rec_count+=1
                        re=evaluate(recommend_list,item_list[j],rec_count,average)   
                        average=re[0]
        

  
    coverage = float(float(rec_count)/float(no_request))
    print "rec_count", rec_count
    print "no request", no_request
    print "Coverage:",coverage
        
def prune(itemset,bucket_size):

    print "Before:",len(itemset)
    for key in itemset.keys():
        value=itemset.get(key)
        frequency=value[0]
        error=value[1]
        if((frequency+error)<=bucket_size):
            del itemset[key]
    print "after:",len(itemset)
    return itemset
        
def recommend(access_upto,itemset):
    length=len(access_upto)
    recommend_list=[]
    recommend_dic={}
    for key in itemset.keys():
        tup1=itemset.get(key)
        item_count=tup1[0]
        item_list=list(key)
        pruned_list=item_list[0:length]
        tup=sublist(access_upto,item_list)
        index=tup[1]+length
        if(tup[0]==1 and (len(item_list)>index)):
            recommend_dic[item_list[index]]=item_count
#            recommend_list.append(item_list[index])
        recommend_list=sorted(recommend_dic.iteritems(), key=lambda (k,v): (v,k))
    recommend_list.reverse()
    len1=len(recommend_list)
    resultlist=[]
    for u in range(0,len1):
        resultlist.append((recommend_list[u])[0])
    return resultlist[0:20]


def sublist(list1,list2):
    output=0
    index=0
#    len_diff=len(list2)-len(list1)SS
    for i in range(0, len(list2)):
        if(list2[i]==list1[0]):
            index=i
            k=0
            if((i+len(list1)<=len(list2))):
                for j in range(i,i+len(list1)):
                    if(list2[j]==list1[k]):
                        output=1
                    else:
                        output=0
                        break
                    k+=1
            else:
                output=0
            break
                               
    return output,index

def evaluate(recommendationlist,actual,count,average):
    correct=0
    if actual in recommendationlist:
        average = calculateAccuracy(1,average,count)
        return (average,count,correct)
    else:
        average=calculateAccuracy(0,average,count)
        return (average,count,correct)
    
def calculateAccuracy(correct,average,count):
        print "In cal average   ",average
#        print "In cal correct   ", correct
#        print "In cal count  " , count
#        print "mid cal1 ", (int(count)-1)*float(average)+int(correct)
        return ((int(count)-1)*float(average)+int(correct))/int(count)

if __name__ == "__main__": try12()
